COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input macro[1,mps]
C00014 ENDMK
C⊗;
\input macro[1,mps]
\input macrwf[1,mps]
\magnification\magstephalf
\baselineskip 14pt
\leftline{\sevenrm B02.Tex[254,rwf]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, December 4, 1989}
\leftline{\sevenrm Unpublished draft}
\centerline{\bf MIDTERM EXAM---INSTRUCTIONS}
\bigskip
There are 9 questions, with a total of 11 parts; each part is worth 10 points.
You may do as many parts as you wish, but your grade will be the sum of the
scores on your 8 best parts.  Exams are due at 11 AM in class, Monday, November
17.  You may use any books and notes you like, but sources must be acknowledged
and proofs must be paraphrased in your own words using the notation and
definitions of this course.  We prefer summary answers written legibly in ink,
backed up by as much rough work as you like to confirm details and resolve
ambiguities.  Prove your answers.
\vfill\eject
\item {1.}{\bf (10 pt)} Let $L$ be the set of strings of A's and B's that contain at
least one of ABBABA or BBAABB.  How many control states does a minimized
deterministic finite recognizer for $L$ have?  Prove your answer.  Brevity will
be appreciated.

\item{2.}{\bf (10 pt)} Let $L$ be a language in which the shortest string has
length $n$.  Show that any nondeterministic program for a finite machine that 
accepts $L$ has at least $n+1$ states.

\item{3.}{\bf (10 pt)} Exhibit a language accepted by a finite machine where the 
required number of states is exactly 10, whether for a deterministic or 
nondeterministic program.

\item {4.}  The {\it signature} of a program is the set of lengths of strings the
program accepts.
\item\item{4A. {\bf(10 pt)}}  Which sets of integers can be the signature of a
deterministic program on a finite machine?
\item\item{4B. {\bf (10 pt)}} Of a nondeterministic program on a one-counter machine?

\item{5.}  A one-counter machine has an oracle that tests whether the number in the
counter is a perfect square or not.
\item\item {5A. {\bf (10 pt)}} Show that there is a nondeterministic program that
accepts $L = \{a↑{i↓{1}}ba↑{i↓{2}} b\cdots a↑{i↓{n}} b$ such that
$n \geq 0$, $0 \leq i↓1 < i↓2 <\cdots < i↓n\}$.
\item\item {5B.{\bf (10 pt)}} Show that there is a nondeterministic program that
accepts the complement of $L$ without using the oracle.

\item {6.}{\bf (10 pt)} Machine $M↓1$ is a one-stack transducer with an oracle that
tests the string in the stack for membership in regular set $R↓1$.  Machine
$M↓2$ is similar, but the oracle tests for regular set $R↓2$.  Show that $M↓1$
and $M↓2$ are equivalent; for every program on one, there is a program on the other
with the same transfer function.  Reminder: ``regular'' means recognized
by a finite machine.

\item {7.} {\bf (10 pt)} Let $L$ be the language $\{xy \in \{A,B\}↑*$ such that
$xy = yx$, $x\not= \Lambda$, $y\not= \Lambda\}$.  Is there a nondeterministic 
one-stack acceptor for $L$?  Prove your answer.

\item {8.}  Let $L$ be any non-empty language (set of strings).
\item\item{8A. {\bf 10 pt)}} Show that the set $\{xa↑i b↑j c↑k$ such that $x\in 
L$, $i > j > k > 0\}$ is not accepted by any (including nondeterministic)
program for a one-stack machine.
\item\item {8B. {\bf (10 pt)}} What if the condition were changed to $i < j < k$?
\item {9.}{\bf (10 pt)} Let $S$ be an infinite set accepted by a given 
nondeterministic Turing machine program.  Show that there is a deterministic
program for a Turing machine, that computes a total function with range $S$.
\vfill\eject
\centerline{\bf MIDTERN SOLUTIONS---FALL 1989}
\bigskip
\item {1.} The various prefixes of ABBABA and BBAABB must leave a recognizer in
different states; for example, ABB reaches a state where ABA is the shortest
input that reaches an accepting state.  (The exception is that ABBABA and BBAABB
may reach the same state.)  The above depends on the unique location of every 
proper prefix and suffix.  So there are at least twelve states.  A recognizer
may achieve this by using as state, after input $x$, the longest suffix of $x$
that is a prefix of ABBABA or BBAABB, and combining the two states where those 
are the suffixes.

\item {2.} If a machine for $L$ has $n$ states or fewer, 
a string of length $n$ ($\geq$ 
the pumping member) can be pumped down, giving a shorter string in $L$.

\item {3.} The language consisting of strings of length $\geq$ 9 is readily
recognized by a 10-state DFR, and by problem 2 requires at least 10 states for a 
NFA.

\item {4.}(A and B)  For any such program, there is a pumping number $n$.  
Any pumpable 
string can be pumped enough to increase its length by $n!$  For each $0 \leq r
< n!$, look at the periodic set $\{r + n + kn!\} = S↓r$; if one member of
$S↓r$ is in the signature, all the larger members are, so $S↓r\cap$ signature is
eventually periodic with period $n!$, and since there are only finitely many
$r$, the signature itself is eventually periodic.  
Any set that is eventually periodic is a signature of a DFR that
looks like
\vskip 0.5in
\item\item  with accepting states scattered around.

\item {5A.} The program that accepts $L$, using nondeterminism, increases the
counter to $i↑2↓k + 1$ before each group of $a's$, and increments twice for
each $a$, checking that this just reaches the next square.

\item {5B.} The program accepts any string that contains $b a↑j b a↑k b$ where
$j \geq k$, or ends in $a$.  Details are easy.

\item {6.} Let $M↓3$ have the oracle for the empty set, so that oracle tests
are redundant.  To simulate a program for $M↓1$ on $M↓3$, use a DFR for
$R↓1$.  When $x$ is the string on the stack, for each prefix $y$ of $x$, keep 
with the last character of $y$ the state that the DFR would be in after reading
$y$.  In particular, the top of the stack includes the state reached by
the DFR on reading $x$, which is accepting iff $x \in R↓1$.

\item {7.} Suppose there is a one stack acceptor (and therefore a generator) for
$L$.  Compose it with a finite transducer that accepts only strings of the
form $A↑iB A↑j B A↑k B$, mapping them into $C↑i D↑j E↑k$.  The only strings in
$L$ that the transducer accepts are $A↑iB A↑iB A↑iB$, so the composite
machine, a one-stack generator, generates $C↑i D↑i E↑i$, which is known to
be impossible.

\item {8A.} Let $p$ be the largest number of $a$'s with which any member of $L$
ends.  Suppose the set defined were accepted, and therefore generated, by a 
one-stack machine.  Compose it with a finite transducer that accepts only
input of the form $y a↑{p+i} b↑j c↑k$ with $y$ not ending in $a$,
writing $a↑i b↑j c↑k$.  This generates $\{a↑i b↑j c↑k \mid i > j > k\}$, a
non-2-pumpable language.  So the set is not accepted by any one-stack machine.

\item {8B.} If $L$ is the language $a↑*$, the set becomes $\{a↑p a↑i b↑j c↑k \mid
i < j < k\} = \{a↑\ast b↑j c↑k\mid 1 \leq j < k\}$, which is accepted by
a DPA.  On the other hand, if $L$ is $\{\Lambda\}$, the set is
$\{a↑i b↑j c↑k \mid i < j < k\}$, not accepted by a DPA.

\item {9.} Let $S$ be accepted by program $P↓1$, and let $x$ be a particular
member of $S$.  Define $P↓2$ to be a program that, on input $y$, checks
whether $y$ is a computation of $P↓1$.  If so, $P↓2$ prints the input of that
computation, thus generating $S$,  If not, $P↓2$ prints $x$, so everything
it prints is in $S$.
\bye